package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.混合背包DP;
import java.util.Scanner;

//未优化代码：
public class dp_7 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();//物品种数
        int V = in.nextInt();//背包容量
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[] s = new int[N + 1];
        int[][] dp = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = in.nextInt();
        }
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= V; j++){
                if (s[i] == -1){
                    //01背包
                    //不选的情况
                    dp[i][j] = dp[i - 1][j];
                    //选的情况
                    if (j >= v[i]){
                        dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - v[i]] + w[i]);
                    }
                }else if(s[i] == 0){
                    //完全背包
                    for (int k = 0; k * v[i] <= j; k++){
                        dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
                    }
                }else{
                    //多重背包
                    for (int k = 0; k <= s[i] && k * v[i] <= j; k++){
                        dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - k * v[i]] + k * w[i]);
                    }
                }
            }
        }
        System.out.print(dp[N][V]);
    }
}




//优化代码：
/*
优化方案：
    1.将dp数组从二维降到一维
    2.对于每种物品的信息读入，可以在dp循环中处理
    3.由于每种物品的信息只在当前循环中有用，所以，可以用三个变量代替三个存储物品信息的数组
*/
//class dp_7{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int N = in.nextInt();//物品种数
//        int V = in.nextInt();//背包容量
//        int v,w,s;
//        int[] dp = new int[V + 1];
//        for (int i = 1; i <= N; i++){
//            v = in.nextInt();
//            w = in.nextInt();
//            s = in.nextInt();
//            for (int j = V; j >= 0; j--){
//                if (s == -1){
//                    //01背包
//                    if (j >= v){
//                        dp[j] = Math.max(dp[j],dp[j - v] + w);
//                    }
//                }else if(s == 0){
//                    //完全背包
//                    for (int k = 0; k * v <= j; k++){
//                        dp[j] = Math.max(dp[j],dp[j - k * v] + k * w);
//                    }
//                }else{
//                    //多重背包
//                    for (int k = 0; k <= s && k * v <= j; k++){
//                        dp[j] = Math.max(dp[j],dp[j - k * v] + k * w);
//                    }
//                }
//            }
//        }
//        System.out.print(dp[V]);
//    }
//}

/*
有 N 种物品和一个容量是 V

的背包。

物品一共有三类：

    第一类物品只能用1次（01背包）；
    第二类物品可以用无限次（完全背包）；
    第三类物品最多只能用 si

    次（多重背包）；

每种体积是 vi
，价值是 wi

。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式

第一行两个整数，N，V

，用空格隔开，分别表示物品种数和背包容积。

接下来有 N
行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i

种物品的体积、价值和数量。

    si=−1

表示第 i
种物品只能用1次；
si=0
表示第 i
种物品可以用无限次；
si>0
表示第 i 种物品可以使用 si

    次；

输出格式

输出一个整数，表示最大价值。
数据范围

0<N,V≤1000

0<vi,wi≤1000
−1≤si≤1000

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

8

 */